Various physical phenomena and social phenomena can be represented by interaction models. The interaction model is a model which is defined by a plurality of nodes constituting the model and an interaction between the nodes and, if necessary, a bias for each node. Various models have been proposed in physics and social science, which can all be interpreted as a form of the interaction model.
As an example of a typical interaction model in the field of physics, an Ising model can be mentioned. The Ising model is a model of statistical mechanics to explain the behavior of a magnetic material. The Ising model is defined by spins having binary values of +1 and −1 (or 0 and 1, up and down), an interaction coefficient indicating an interaction between spins, and an external magnetic field coefficient for each spin.
The Ising model can calculate an energy at that time, from the spin arrangement, the interaction coefficient, and the external magnetic field coefficient, which are given. The energy function of the Ising model is generally expressed by the following expression.
      [          Expression      ⁢                          ⁢      1        ]                                            H            ⁡                          (              σ              )                                =                                    -                                                ∑                                      i                    <                    j                                                  ⁢                                                      J                                          i                      ,                      j                                                        ⁢                                      σ                    i                                    ⁢                                      σ                    j                                                                        -                                          ∑                i                            ⁢                                                h                  i                                ⁢                                  σ                  i                                                                                          (          1          )                    
In addition, σi and σj represent the values of i-th and j-th spins, respectively, Ji, j represents an interaction coefficient between the i-th and j-th spins, hi represents the external magnetic field coefficient for the i-th spin, σ represents the spin arrangement.
In Expression (1), the first term is to calculate the energy resulting from the interaction between spins. In general, the Ising model is expressed as an undirected graph, and it does not distinguish between the interaction from the i-th spin to the j-th spin and the interaction from the j-th spin to the i-th spin. Therefore, in the first term, the influence of the interaction coefficient is calculated for combinations of σi and σj satisfying i<j. The second term is to calculate the energy resulting from the external magnetic field for each spin.
The ground-state search of Ising model is an optimization problem to find a spin arrangement that minimizes the energy function (also referred to as Hamiltonian in general) of the Ising model. It is known that the ground-state search of Ising model represented by a nonplanar graph is NP hard. In recent years, a device that searches for a ground state in order to solve this problem efficiently has been proposed (PTL 1).